(1) Field of the Invention
The present invention relates to compilers, and more specifically to an optimizing compilation technique for improving execution speeds.
(2) Description of the Related Art
Conventionally, in order to improve the performance of programs installed in a computer system that processes massive data, an optimizing compiler is used to optimize such a program to shorten the program execution time.
One optimization method is instruction scheduling that reorders program statements to improve the execution efficiency.
Upon the optimization, a compiler analyzes the control flow of a program focusing on branches and branch targets to divide the program into units called basic blocks. A basic block is a sequence of consecutive statements containing no branches and merges, and thus executed from the beginning to the end in order. Yet, each basic block may contain a branch at the end.
Since basic blocks contain no branches and merges in a middle, instruction scheduling within each basic block is readily carried out. It should be noted, however, that the local optimization within basic blocks produces only a limited effect. For this reason, it is desirable to expand basic blocks, so that instruction scheduling takes place within a wider range of the program.
Regarding a program containing multiple branches, it may be known that which of the execution paths is frequently executed (such an execution path is hereinafter referred to as a “hot path”). According to one known method, statements on a hot path are moved so as to expand a basic block to increase the execution efficiency of the hot path (See “Compiler Configuration & Optimization” by Ikuo NAKATA, Published by Asakura Shuppan in 2004, pp. 358-381).
Here, a description is given to how to expand a basic block residing on a hot path, taking a program shown in FIG. 5A as an example. FIG. 5A shows part of the program, whereas FIG. 5B shows a control flow graph, which is a representation of the control flow, of the program. In the graph, edges connecting basic blocks B1-B7 represent branches and merges. In this example, an execution path represented by a dashed allow 200 that sequentially connects the basic blocks B1, B2, B4, B5 and B7 is a hot path.
As shown in FIG. 6, a statement S8 included in the basic block B4 is moved into the basic block B2. Next, for a path branched from the basic block B3 to the basic block B4, a statement S81 is generated by duplicating the statement S8 and inserted into the basic block B3 (FIG. 7). With this arrangement, the basic block B2 residing on the hot path is expanded while maintaining the program integrity.
However, there is a problem in a case shown in FIG. 8 where a statement S10 is moved from the basic block B5 to the basic block B2. Suppose, an execution path is taken sequentially from the basic blocks B1, B2, and B4, and a branch condition of a statement S9 in the basic block B4 is false. In this case, a variable “a” referenced by a statement S12 in the basic block B6 must hold a value defined by a statement S1 in the basic block B1. However, the variable “a” holds a value defined by the statement S10 having been moved into the basic block B2. As a result, the program integrity is no longer maintained.
As described above, there may be a case where data dependency present in a program may not be ensured if a statement is moved across a basic block of which last statement is a branch instruction. In such a case, reordering of the statements is restricted and thus the basic blocks cannot be expanded.